A polling based communication infrastructure may be used for the wireless communication of data and voice between devices. One method of achieving this is through the use of Bluetooth, an open specification for wireless communication. Bluetooth is a wireless personal area network (PAN) technology for short-range transmission of digital voice and data between mobile devices (e.g., laptops, PDAs, phones) and desktop devices. Bluetooth supports point-to-point and multipoint applications and is described in further detail in the Bluetooth Baseband Specification 1.1 by the Bluetooth Special Interest Group (SIG), which in expressly incorporated by reference in its entirety. Of a historical note, the name “Bluetooth” is derived from the 10th century King of Denmark, Harald Bl{dot over (a)}tand, alias Bluetooth, who introduced Christianity to Denmark.
The emergence of Bluetooth as a default radio interface in various types of devices provides an opportunity to turn them from stand-alone tools into networked equipment. Bluetooth offers a number of advantages over conventional wireless technologies. For example, unlike conventional infrared data transmission techniques which require line-of-sight between devices, Bluetooth uses omnidirectional radio waves that can transmit through walls and other nonmetal barriers. To counteract interference from outside sources or from other devices, Bluetooth units downgrade the transmission rate instead of halting transmissions altogether. However, there are also a number of new challenges associated with the Bluetooth technology, partly stemming from the fact that Bluetooth was originally developed for single hop wireless connections.
Bluetooth systems, in accordance with the Bluetooth Baseband Specification 1.1, use short range radio technology operating in the unlicensed 2.4 GHz Industrial-Scientific-Medical (ISM) band using a frequency hopping scheme. The hopping is performed on 79 RF channels spaced 1 MHz apart using a frequency hopping spread spectrum technique that changes its signal 1600 times per second. Bluetooth provides considerable data transfer capability at short ranges; e.g., up to 720 Kbps within 10 meters and up to 100 meters with a power boost. The Bluetooth system provides full-duplex transmission based on slotted Time Division Duplex (TDD) scheme, where each slot is 0.625 ms long.
FIG. 1 depicts an exemplary Bluetooth piconet. Bluetooth (BT) units are organized into “piconets” which are collections of devices connected in an ad hoc fashion. Bluetooth piconets are “ad hoc” in that Bluetooth units are free to enter and leave, that is, the piconets are not fixed networks. A piconet is initially formed with two connected devices, herein referred to as “nodes”. One Bluetooth device in each piconet acts as the master, and can have any number of slaves, out of which up to seven can be active simultaneously. The piconet in the figure has one master node, BT 11, and one slave node, BT 12. A “master” is the device in a piconet whose clock and hopping sequence are used to sequence other devices in piconet. A “slave” is any other device in the piconet. The terms “master” and “slave” are defined as logical states, in that a particular Bluetooth device can be a master or a slave. In fact, a Bluetooth unit can simultaneously be a master in one piconet and a slave in one or more other piconets.
FIG. 2 illustrates a piconet with a master node 21 and a plurality of slave nodes 22–28 arranged in a star network topology. In a Bluetooth system, a slave node can only communicate directly with its master node. If slave node 22 wishes to communicate with slave node 26, slave node 22 would have to transmit the information it wished to communicate to master node 21. Master node 21 would then transmits the information to slave node 26. In addition to being classified as a master node and slave node, a node may be classified as an idle node. An idle node is a node which is not currently participating in a piconet.
The communication within a piconet is organized by the master which polls each slave according to some polling scheme. Master-to-slave transmissions always start in an even-numbered time slot, while slave-to-master transmissions always start in an odd-numbered time slot. A “frame” includes a pair of corresponding master-to-slave and slave-to-master slots. A master has frames which are in common with those of its slaves since a master's clock and hopping sequence are used to sequence its slaves. A slave is only allowed to transmit in the current slave-to-master slot if it has been polled by the master in the previous master-to-slave slot. The master may or may not include data in the packet used to poll a slave. Bluetooth packets can be one, three or five slots long and they can carry synchronous data (e.g., real-time traffic such as voice data) on Synchronous Connection Oriented (SCO) links. Bluetooth packets can also be used to communicate asynchronous data (e.g., elastic data traffic which tend to be less sensitive to delays) on Asynchronous Connectionless (ACL) links.
FIG. 3 depicts an exemplary scatternet comprising piconet 1, piconet 2 and piconet 3. A scatternet is formed by multiple independent and unsynchronized piconets. A Bluetooth unit can participate in (e.g., belong to, or be a member of) more than one piconet at any time, but it can be a master in only one piconet. A Bluetooth unit can be a master of one piconet and also be a slave of one or more other piconets. A unit that simultaneously belongs, or may belong, to more than one piconet is a Participant in Multiple Piconets (PMP) node. Since Bluetooth units can transmit or receive in only one piconet at a single point in time, PMPs switch between piconets on a time division basis. That is, a PMP switches back and forth between piconets to communicate in one or the other, hence abiding by the premise that a Bluetooth unit can transmit or receive in only one piconet at a single point in time. A set of independent, non-synchronized piconets that are interconnected is referred to as a “scatternet” network. Since different piconets are not synchronized in time, a PMP tends to lose some time when switching from one piconet to another. Furthermore, the temporal unavailability of PMP nodes must be taken into account when coordinating the communication with them. The inefficiencies of switching between piconets present a significant constraint in building scatternets.
The piconet 1 of FIG. 3 includes a master node 33, and the slave nodes 31, 32 and 34. The piconet 2 includes the master node 35, and the slave nodes 34, 36, 37 and 38. The piconet 3 includes the master node 39, and the slave nodes 38, 40 and 41. PMP nodes 34 and 38 are used to implement the scatternet shown in the figure. If, for example, node 31 wishes to communicate with node 40, then nodes 34 and 38 might act as bridging nodes by forwarding packets between the two piconets and in particular between nodes 31 and 40. Node 31 transfers the information to node 33, the master node of piconet 1. Master node 33 transmits the information to forwarding node 34. Forwarding node 34 then forwards the information to master node 35, which in turn, transmits the information to forwarding node 38. Forwarding node 38 forwards the information to master node 39 which transmits the information to the destination node 40.
Each Bluetooth unit has a globally unique 48 bit IEEE 802 address. This address, called the Bluetooth Device Address (e.g., BD_ADDR) is initially assigned at the time the Bluetooth unit is manufactured. In addition, the Master of a piconet assigns a local active member address (e.g, AM_ADDR) to each active member of the piconet. The AM_ADDR, which is only three bits long, is dynamically assigned and deassigned and is unique only within a single piconet. The master uses the AM_ADDR when polling a slave in a piconet. However, when the slave, triggered by a packet from the master addressed with the slave's AM_ADDR, transmits a packet to the master, it includes its own AM_ADDR (not the masters) in the packet header.
Even though all data is transmitted in packets, the packets can carry both synchronous data, on Synchronous Connection Oriented (SCO) links which is mainly intended for voice traffic, and asynchronous data, on asynchronous connectionless links (ACL) links. Depending on the type of packet that is used, an acknowledgment and retransmission scheme is used (not for SCO packets transferring synchronous data) to ensure reliable data transfer, as well as forward error correction (FEC) in the form of channel coding.
A Bluetooth unit participating in multiple piconets does so on a time division basis. Hence, its presence in the different piconets must be controlled by some scheduling mechanism. Such scheduling is denoted interpiconet scheduling as opposed to intrapiconet scheduling which is a mechanism controlling the master's polling of its slaves.
Interpiconet scheduling is perceived as one of the greatest obstacles on Bluetooth's path to success. Due to the need to synchronize its radio from one piconet to another, a Bluetooth unit necessarily loses some time while switching, which represents an important performance constraint in scheduling the scatternet. Furthermore, the temporal unavailability of PMP nodes must be taken into account when coordinating the communication with them. The inefficiencies of interpiconet communication present a significant constraint in building scatternets.
There are two effects that can significantly reduce the efficiency of the polling based communication in Bluetooth scatternets. First, nodes that have no data to transmit may be unnecessarily polled, while other nodes with data to transmit may have to wait to be polled. Second, at the time of an expected poll one of the nodes of a communicating node pair may not be present in the piconet. For example, the slave that is being polled may not be listening, or the slave expecting to be polled is not polled by its master. Both situations give rise to inefficiencies in carrying out communications.
One primary problem in interpiconet communication arises in trying to effectively coordinate the presence of PMP nodes in different piconets such that the occurrence of timing conflicts is minimized. A conflict occurs if a PMP node is assumed to be active by one or more of those piconets it participates in, but the PMP node is out of the piconets or otherwise unavailable. It can be equivalently disadvantageous if the PMP node is active in one of the piconets that assumes the PMP node to be inactive at that time. These are not the only issues leading to inefficiencies in an interpiconet scheduler. For example, the pre-scheduling and the intrapiconet communication should also be considered.
The timing of reaction time is a common idealization which does not always reflect real-world conditions. For instance, designs of Bluetooth scheduling algorithms often assume that the scheduler reacts in frame f(n+1) to occurrences in frame f(n). However, due to the non-ideal nature of electronic hardware, it is often not possible to react that fast. In effect, what happens in frame f(n) will generally not affect the schedule until k frames later, i.e., frame f(n+k), where k>>1. Such delay can, for example, be introduced by batched scheduling. Batched scheduling means that instead of scheduling frames one by one in a continuous flow, a schedule is computed for a number of frames; e.g., a batch of frames is scheduled all at once. While one batch is being executed the next batch is computed. Since the frames are batched for execution rather than continuously scheduling them, a delay is introduced which leads to inefficiencies in the system.
The fundamental building block in Bluetooth is the piconet. One system for intrapiconet scheduling is the Fair Exhaustive Polling system (FEP). Such schedulers divide the capacity within the piconet according to the dynamic bandwidth demands of the traffic. However, interpiconet scheduling is still needed to enable devices to simultaneously participate in multiple piconets. In fact, even for devices with interpiconet scheduling capabilities most traffic tends to be contained within one piconet. That is, large portions of their time will be as members of one piconet. The importance of efficient intrapiconet scheduling will not decrease when interpiconet scheduling is introduced, and therefore an interpiconet scheduler must not deteriorate the intrapiconet scheduler.